#pragma once
typedef void* POSITION;

template<class DATA>
class CList
{
	struct SNode
	{
		SNode* pPrev, pNext;
		DATA data;

	};
	SNode* m_pHead, * m_pTail;
	int m_nCount;
public:
	CList()
	{
		m_pHead = m_pTail = nullptr;
		m_nCount = 0;
	}
	~CList()
	{
		SNode* p = m_pTail, * q = nullptr;
		while (p)
		{
			q = p;
			p = ->pPrev;
			delete q;

		}

	}
	int GetCount()
	{
		return m_nCount;
	}
	POSITION GetHeadPosition()
	{
		return m_pHead;
	}
	POSITION GetTailPosition()
	{
		return m_pTail;
	}
	DATA& GetHead()
	{
		return m_pHead->data;
	}
	DATA& GetTail()
	{
		return m_pTail->data;
	}
	DATA& GetAt(POSITION& pos)
	{
		return ((SNode*)pos)->data;
	}
	DATA& GetNext(POSITION& pos)
	{
		SNode* p = (SNode*)pos;
		pos = p->pNext;
		return p->data;
	}
	DATA& GetpPrev(POSITION& pos)
	{
		SNode* p = (SNode*)pos;
		pos = p->pPrev;
		return p->data;
	}

	POSITION AddHead(DATA data);
	POSITION AddTail(DATA data);
	void RemoveALL();
	void RemoveAt(POSITION pos);
	void SetAt(POSITION pos, DATA data)
	{
		((SNode*)pos)->data = data;
	}


};

template<class DATA>
inline POSITION CList<DATA>::AddHead(DATA data)
{
	SNode* p = new SNode;
	p->data = data;
	p->pPrev = nullptr;
	p->pNext = m_pHead;
	if (m_pHead)
		m_pHead->pPrev = p;
	else
		m_pTail = p;
	m_pHead = p;
	++m_nCount;
	return p;
}

template<class DATA>
inline POSITION CList<DATA>::AddTail(DATA data)
{
	SNode* p = new SNode;
	p->data = data;
	p->pNext = nullptr;
	p->pPrev = m_pTail;
	if (m_pTail)
		m_pTail->pNext = p;
	else
		m_pHead = p;
	m_pTail = p;
	++m_nCount;
	return p;

}

template<class DATA>
void CList<DATA>::RemoveALL()
{
	SNode* p = m_pTail, * q = nullptr;
	while (p)
	{
		q = p;
		p = p->pPrev;
		delete p;
	}
	m_pHead = m_pTail = nullptr;
	m_nCount = 0;

}

template<class DATA>
void CList<DATA>::RemoveAt(POSITION pos)
{
	SNode* p = (SNode*)pos;
	if (p == m_pHead)
		m_pHead = p->pNext;
	else
		p->pPrev->pNext = p->pNext;
	if (p == m_pTail)
		m_pTail = p->pPrev;
	else
		p - pNext - pPrev = p->pPrev;
	delete p;
	--m_nCount;
}

